//链栈基本运算算法
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define MAXSIZE 100
typedef char ElemType;
enum{
	NONE = 0,
	SMALL,
	MIDDLE,
	LARGE
};
typedef struct linknode
{	
	ElemType data;				//数据域
	struct linknode *next;		//指针域
} LinkStNode;					//链栈类型
void InitStack(LinkStNode *&s)
{
	s=(LinkStNode *)malloc(sizeof(LinkStNode));
	s->next=NULL;
}
void DestroyStack(LinkStNode *&s)
{
	LinkStNode *p=s->next;
	while (p!=NULL)
	{	
		free(s);
		s=p;
		p=p->next;
	}
	free(s);	//s指向尾结点,释放其空间
}
bool StackEmpty(LinkStNode *s)
{
	return(s->next==NULL);
}
void Push(LinkStNode *&s,ElemType e)
{	LinkStNode *p;
	p=(LinkStNode *)malloc(sizeof(LinkStNode));
	p->data=e;				//新建元素e对应的结点p
	p->next=s->next;		//插入p结点作为开始结点
	s->next=p;
}
ElemType Pop(LinkStNode *&s)
{
	LinkStNode *p;
	ElemType e = '\0';
	if (s->next==NULL)		//栈空的情况
		return '\0';
	p=s->next;				//p指向开始结点
	e=p->data;
	s->next=p->next;		//删除p结点
	free(p);
	return e;
}	

ElemType GetTop(LinkStNode *s)
{	if (s->next==NULL)		//栈空的情况
		return '\0';
	
	return s->next->data;
}

int checkBrackets(const char *expr)
{
	LinkStNode*s;
	InitStack(s);
	int flag = 3;
	for(int i = 0;expr[i]!='\0';i++)
	{
		char c = expr[i];
		if(c=='(')
		{
			Push(s,c);
			flag = 1;
		}
		else if(c=='[')
		{
			Push(s,c);
			
			if(flag<2) return 0;
			flag = 2;
		} 
		else if(c=='{')
		{
			Push(s,c);
			if(flag<3) return 0;
		}
		else if(c==')')
		{
			if(s->next==NULL) return 0;
			char open = Pop(s);
			if(open!='(')
			{
				DestroyStack(s);
				return 0;//括号不匹配
			}
			else if(open=='(')
			{
				
				if(s->next!=NULL&&s->next->data=='[') flag = 2;
				if(s->next!=NULL&&s->next->data=='{') flag = 3;
			}
			
		}
		else if(c==']')
		{
			if(s->next==NULL) return 0;
			char open = Pop(s);
			if(open!='[')
			{
				DestroyStack(s);
				return 0;//括号不匹配
			}
		}
		else if(c=='}')
		{
			if(s->next==NULL) return 0;
			char open = Pop(s);
			if(open!='{')
			{
				DestroyStack(s);
				return 0;//括号不匹配
			}
		}
		
		if(s->next==NULL)
			flag = 3;
	}
	
	
	if(s->next==NULL)
	{
		DestroyStack(s);
		return 1;
	}
	else {
		DestroyStack(s);
		return 0;
	}
}

//表达式是否合法
int isValidExpression(const char *expr)
{
	int len = strlen(expr);
	if(len==0) return 0;
	
	for (int i = 0; i < len; i++) {
		
		char c = expr[i];
		
		if ((c<48) && (c>57) && c != '+' && c != '-' && c != '*' && c != '/' &&
			c != '(' && c != ')' && c != '[' && c != ']' && c != '{' && c != '}') {
			return 0; // 包含非法字符
		}
		
// 检查操作符和操作数的合法顺序
		if (i > 0 && ((c == '+' || c == '-' || c == '*' || c == '/') &&
			(expr[i - 1] == '+' || expr[i - 1] == '-' || expr[i - 1] == '*' || expr[i - 1] == '/'))) {
			return 0; // 连续操作符
		}
		
		if (i > 0 && ((c == ')' || c == ']' || c == '}') && 
			(expr[i - 1] == '+' || expr[i - 1] == '-' || expr[i - 1] == '*' || expr[i - 1] == '/'))) {
			return 0; // 闭括号前不能是操作符
		}
		
		if (i < len - 1 && (c == '(' || c == '[' || c == '{') &&
			(expr[i + 1] == '+' || expr[i + 1] == '-' || expr[i + 1] == '*' || expr[i + 1] == '/')) {
			return 0; // 开括号后不能是操作符
		}
		if(i < len-1 && (c == '/')&&expr[i+1]=='0')
		{
			return 0;//不能除0
		}
	}
	return 1;
}

int applyOp(int a, int b, char op)
{
	switch (op)
	{
		case '+': return a + b;
		case '-': return a - b;
		case '*': return a * b;
		case '/': return a / b;
	}
	return 0;
}

// 计算表达式的值（使用逆波兰表示法）
int precedence(char op)
{
	if (op == '+' || op == '-') return 1;
	if (op == '*' || op == '/') return 2;
	return 0;
}

int evaluateExpression(const char *expr)
{
	LinkStNode*sta,*ops;
	InitStack(sta);
	InitStack(ops);
	int len = strlen(expr);
	for(int i = 0;expr[i]!='\0';i++)
	{
		if (expr[i]>47&&expr[i]<58) {
			int val = 0;
			while (i < len && expr[i]>47&&expr[i]<58) {
				val = val * 10 + (expr[i] - '0');
				i++;
			}
			i--; // 调整 i 位置
			Push(sta, val);	
		}
		else if(expr[i] == '(' || expr[i] == '[' || expr[i] == '{') {
			Push(ops, expr[i]);
		}
		else if (expr[i] == ')' || expr[i] == ']' || expr[i] == '}') {
			while (ops->next!=NULL && GetTop(ops) != '(' && GetTop(ops) != '[' && GetTop(ops) != '{') {
				int val2 = Pop(sta);
				int val1 = Pop(sta);
				char op = Pop(ops);
				Push(sta, applyOp(val1, val2, op));
			}
			Pop(ops); // 弹出开括号
		} 
		else {
			while (ops->next!=NULL&& precedence(GetTop(ops)) >= precedence(expr[i])) {
				int val2 = Pop(sta);
				int val1 = Pop(sta);
				char op = Pop(ops);
				Push(sta, applyOp(val1, val2, op));
			}
			Push(ops, expr[i]);
		}
	}
	
	while (ops->next!=NULL) {
		int val2 = Pop(sta);
		int val1 = Pop(sta);
		char op = Pop(ops);
		Push(sta, applyOp(val1, val2, op));
	}
	
	return Pop(sta); // 返回结果
	
	
}


int main()
{
	char expr[MAXSIZE];
	printf("请输入中缀表达式：");
	fgets(expr,sizeof(expr),stdin);
	
	//去掉末尾换行符
	int len = strlen(expr);
	if(len>0&&expr[len-1]=='\n')
	{
		expr[len-1] = '\0';
	}
	//括号是否匹配 -> 表达式是否合法 -> 计算结果
	if(checkBrackets(expr)==1)
	{
		printf("括号匹配且合法\n");
		//表达式是否合法
		if(isValidExpression(expr)==1){
			printf("表达式合法\n");
			//计算表达式的值
			int result = evaluateExpression(expr);
			printf("表达式的计算结果是: %d\n", result);
		}
		
		else printf("表达式不合法\n");
	}
	else {
		printf("括号不匹配或不合法\n");
	}
	return 0;
}
